<!DOCTYPE html>
<html>
<head></head>
<body>
<script>
    var array = [1, 3, 5, 7, 9, 2, 4, 6, 8];
    /* O(N^2)
     ----------------------------------------------*/
    var bubbleSort = function (arr) {
        if (!Array.isArray(arr) || arr.length < 2) return arr;
        var n = arr.length;
        for (var i = 0; i < n - 1; i++) {
            for (var j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    var tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    };
    // bubbleSort(array);

    var selectionSort = function (arr) {
        if (!Array.isArray(arr) || arr.length < 2) return arr;
        var n = arr.length;
        for (var i = 0; i < n - 1; i++) {
            var k = i;
            var min = arr[i];
            for (var j = i + 1; j < n; j++) {
                if (arr[j] < arr[k]) {
                    min = arr[j];
                    k = j;
                }
            }
            var tmp = arr[i];
            arr[i] = min;
            arr[k] = tmp;
        }
        return arr;
    };
    // selectionSort(array);

    var insertionSort = function (arr) {
        if (!Array.isArray(arr) || arr.length < 2) return arr;
        var n = arr.length;
        for (var i = 0; i < n; i++) {
            var k = i;
            while (k > 0) {
                if (arr[k - 1] > arr[k]) {
                    var tmp = arr[k - 1];
                    arr[k - 1] = arr[k];
                    arr[k] = tmp;
                    k--
                } else {
                    break;
                }
            }
        }
    };
    // insertionSort(array);

    /* O(N*logN)
     ----------------------------------------------*/
    var mergeSort = function (arr) {
        if (!Array.isArray(arr) || arr.length < 2) return arr;
        var n = arr.length;
        var merge = function (first, mid, last) {
            var tmp = [];
            var i = first;
            var j = mid + 1;
            while (i <= mid && j <= last) {
                if (arr[i] < arr[j]) {
                    tmp.push(arr[i]);
                    i++;
                } else {
                    tmp.push(arr[j]);
                    j++;
                }
            }
            while (i <= mid) {
                tmp.push(arr[i]);
                i++;
            }
            while (j <= last) {
                tmp.push(arr[j]);
                j++;
            }
            for (var k = 0, l = tmp.length; k < l; k++) {
                arr[first + k] = tmp[k];
            }
        };
        var sort = function (i, j) {
            if (i < j) {
                var mid = Math.floor((i + j) / 2);
                arguments.callee(i, mid);
                arguments.callee(mid + 1, j);
                merge(i, mid, j);
            }
        };
        sort(0, n - 1);
        return arr;
    };
    // mergeSort(array);

    var quickSort = function (arr) {
        if (arr.length <= 1) return arr;
        var n = arr.length;
        var pivotIndex = Math.floor(n / 2);
        var pivot = arr.splice(pivotIndex, 1)[0];
        var left = [];
        var right = [];
        for (var i = 0; i < n; i++) {
            if (arr[i] <= pivot) left.push(arr[i]);
            else right.push(arr[i]);
        }
        return quickSort(left).concat(pivot, quickSort(right));
    };
    // quickSort(array);

    var shellSort = function (arr) {
        if (!Array.isArray(arr) || arr.length < 2) return arr;
        var n = arr.length;
        var swap = function (array, i, j) {
            var tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        };
        var gap = Math.floor(n / 2);
        while (gap > 0) {
            for (var i = gap; i < n; i++) {
                for (var j = i; j > 0; j -= gap) {
                    if (arr[j - gap] > arr[j]) {
                        swap(arr, j - gap, j)
                    } else {
                        break;
                    }
                }
            }
            gap = Math.floor(gap / 2);
        }
        return arr;
    };
    shellSort(array);

    console.log(array);
</script>
</body>
</html>